The present invention relates to an image processing device and, more particularly, to an image processing device, such as a computer aided design device, adapted to process pixel line data of an input drawing, including tracing the pixels, converting them into polygonal line data efficiently, and executing polygonal line processing stably to form a polygonal line data with a small transformation in a curved segment of an image.
In the computer aided design device, when drawing data is processed by digitizing a line drawing, a variety of shapes are extracted from the drawing in which various line segments are present. These segments are classified into drawing elements. As a pre-processing of the image processing, after the line drawing is read by a scanner and stored as pixel line data of a dot line image in a memory unit, the pixel line data is subjected to polygonal line processing for conversion into polygonal line data, thus approximating the drawing into a polygonal line by means of the polygonal line processing and classifying it into a drawing element.
The polygonal line processing for converting the pixel line data into polygonal line data is executed by a series of three processing steps in order, which include trace processing of a pixel line, polygonal line converting processing of the traced pixel line, and polygonal lines connecting processing. The trace processing of the pixel line is designed so as to form tracing dot data by tracing one pixel of the pixel line after another and to suspend the tracing when a branch point or a terminal point is detected. The polygonal line converting processing is to form a polygonal line from the tracing dot data for each of the traced pixel lines. The polygonal lines connecting processing is designed so as to connect each of the polygonal lines to form continuous polygonal line data, thus executing the polygonal line processing for conversion of the pixel line data into polygonal line data.
It is to be noted, however, that, in the polygonal line processing for converting the pixel line data into the polygonal line data, the trace processing of the pixel line stops at the branch point or the terminal point. Therefore, even if a pixel line of a dot line image in the neighborhood of a branch point continues in a direction in which the pixel line has been traced until then, the tracing is forced to stop at the branch point and thereafter the tracing dot data so far done is subjected to the processing for formation of a polygonal line. Then another trace processing of the pixel line begins from that branch point to form another polygonal line. Thereafter, the two polygonal lines are connected at the subsequent polygonal lines connecting processing. Accordingly, if a line extends in a straight direction, however, the pixel line cannot be continuously traced so that such a straight line cannot be formed by one trace processing. As a result, a number of connections with the polygonal lines connecting processing are required in the polygonal line processing, thus requiring a longer processing period of time for conversion into a polygonal line.
As shown in FIG. 9, for example, there is a technique of polygonal line processing for converting pixel line data into polygonal line data, which involves extracting as a polygonal line structuring point a pixel b(k) from a segment of a given pixel line b(m) of pixel line data from a drawing segmented by two given pixels b(i) and b(j) which are located at the i-th and j-th positions of the pixel line b(m), respectively, the pixel b(k) being in a distance most remote from and perpendicular to a straight line connecting the pixels b(i) and b(j) and apart in a distance equal to or longer than a constant distance, and converting the polygonal line structuring points into a polygonal line.
In approximating a drawing into a polygonal line by extracting polygonal line structuring points and converting them into a polygonal line by this polygonal line processing technique, an optimum pixel is designed so as to be extracted as a polygonal line structuring point from a pixel line of the pixel line data. However, a polygonal line is likely to be transformed at a curved portion of a drawing on account of a deviation in coordinates of pixels themselves due to digital noises so that it is hard to provide polygonal line data with a stable approximation of a polygonal line.